package m202406.d29;

import java.util.Arrays;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/6/29 15:44
 */
public class Q215 {

    public static void main(String[] args) {
        Q215 q215 = new Q215();
        int[] ints = new int[]{1, 3, 2};
        q215.buildHeap(ints);
        System.out.println(Arrays.toString(ints));
    }

    public int findKthLargest(int[] nums, int k) {
        buildHeap(nums);
        int size = nums.length;
        for (int i = 0; i < k - 1; i++, size--) {
            down(nums, size);
        }
        return nums[0];
    }

    private void buildHeap(int[] nums) {
        for (int i = nums.length-1; i >=0; i--) {
            down(nums, i, nums.length);
        }
    }

    private void down(int[] nums, int size) {
        nums[0] = nums[size - 1];
        down(nums, 0, size - 1);
    }

    private void down(int[] nums, int index, int size) {
        int left = left(index);
        int right = right(index);

        int next = index;

        if (left < size && nums[left] > nums[next]) {
            next = left;
        }

        if (right < size && nums[right] > nums[next]) {
            next = right;
        }
        if (next < size && next != index) {
            swap(nums, index, next);
            down(nums, next, size);
        }
    }

    private int left(int i) {
        return i * 2 + 1;
    }

    private int right(int i) {
        return i * 2 + 2;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
